package cn.suchan.jianzhi.q16_merge;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 知识点：合并两个排序的链表
 * 题目描述
 * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则
 *
 * @author suchan
 * @date 2019/05/26
 */
public class Solution {

    /**
     * 方法一：借助list进行排序，但是我没找到链表头
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }

        // 先把list1和list2拼接起来再排序
        ListNode tempNode = list1;
        ListNode tempNext = list1.next;
        while (tempNext != null) {
            tempNode = tempNext;
            tempNext = tempNext.next;
        }
        tempNode.next = list2;

        // 由于链表无法获取到当前节点的前一个节点，无法接触它们之间的关系，所以不能直接排序
        List<ListNode> tempList = new ArrayList<>();
        ListNode temp = list1.next;
        while (temp != null) {
            tempList.add(temp);
            temp = temp.next;
        }

        for (int i = 0; i < tempList.size() - 1; i++) {
            for (int j = i + 1; j < tempList.size(); j++) {
                if (tempList.get(i).val > tempList.get(j).val) {
                    tempList.get(i).next = tempList.get(j).next;
                    tempList.get(j).next = tempList.get(i);
                    if (i > 0) {
                        tempList.get(i - 1).next = tempList.get(j);
                    }
                    // List互换位置
                    Collections.swap(tempList, i, j);
                }
            }
        }
        return list1;
    }

    /**
     * 方法二：递归排序
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode Merge1(ListNode list1, ListNode list2) {
        ListNode listNode = null;
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        if (list1.val <= list2.val) {
            listNode = list1;
            listNode.next = Merge1(list1.next, list2);
        } else if (list1.val > list2.val) {
            listNode = list2;
            listNode.next = Merge1(list1, list2.next);
        }
        return listNode;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(10);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(6);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode node6 = new ListNode(7);
        ListNode node7 = new ListNode(2);
        ListNode node8 = new ListNode(9);
        ListNode node9 = new ListNode(8);
        ListNode node10 = new ListNode(4);

        node6.next = node7;
        node7.next = node8;
        node8.next = node9;
        node9.next = node10;

        ListNode merge = solution.Merge1(node1, node6);
        System.out.println(merge.val);
    }
}
